package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1053 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[] prevPermOpt1(int[] arr) {
            if (arr.length <= 1) return arr;
            Stack<Integer> stack = new Stack<>();
            stack.push(arr.length - 1);
            int i = arr.length - 2;
            for (; i >= 0; i--) {
                if (arr[i] == arr[stack.peek()]) {
                    stack.pop();
                    stack.push(i);
                } else if (arr[i] < arr[stack.peek()]) stack.push(i);
                else break;
            }

            if (-1 == i) return arr;
            // i 位置需要和stack中的位置替换
            int swapPos = stack.peek(), temp = 0;
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) swapPos = stack.pop();
            temp = arr[i];
            arr[i] = arr[swapPos];
            arr[swapPos] = temp;
            return arr;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.prevPermOpt1(InputUtil.toIntegerArray("[1,2,3]"))));
        System.out.println(Arrays.toString(solution.prevPermOpt1(InputUtil.toIntegerArray("[3,2,1]"))));
        System.out.println(Arrays.toString(solution.prevPermOpt1(InputUtil.toIntegerArray("[1,1,5]"))));
        System.out.println(Arrays.toString(solution.prevPermOpt1(InputUtil.toIntegerArray("[1,9,4,6,7]"))));
        System.out.println(Arrays.toString(solution.prevPermOpt1(InputUtil.toIntegerArray("[3,1,1,3]"))));
    }

    public static void main(String[] args) throws Exception {
        LC1053 an = new LC1053();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
